#include <bits/stdc++.h>
using namespace std;

class DoubleEndedStack {
	private:
	    vector<int> data;
	    int top1, top2;
	    
	    void resize() {
	        vector<int> newData(data.size() * 2);
	        for (int i = 0; i <= top1; ++i) 
	            newData[i] = data[i];
	        int newRightStart = newData.size() - (data.size() - top2);
	        for (int i = top2; i < data.size(); ++i) 
	            newData[newRightStart + i - top2] = data[i];
	        top2 = newRightStart;
	        data = newData;
	    }
	
	public:
	    DoubleEndedStack(int initSize = 100) : data(initSize), top1(-1), top2(initSize) {}
	
	    bool pushLeft(int x) {
	        if (top1 + 1 == top2) resize();
	        data[++top1] = x;
	        return true;
	    }
	
	    bool pushRight(int x) {
	        if (top2 - 1 == top1) resize();
	        data[--top2] = x;
	        return true;
	    }
	
	    int popLeft() {
	        if (top1 == -1) throw runtime_error("Left stack empty");
	        return data[top1--];
	    }
	
	    int popRight() {
	        if (top2 == data.size()) throw runtime_error("Right stack empty");
	        return data[top2++];
	    }
	
	    int peekLeft() const {
	        if (top1 == -1) throw runtime_error("Left stack empty");
	        return data[top1];
	    }
	
	    int peekRight() const {
	        if (top2 == data.size()) throw runtime_error("Right stack empty");
	        return data[top2];
	    }
};
